
import math

# https://leetcode-cn.com/problems/max-points-on-a-line/
# 找出在同一直线的最多点数（如果有重复也算）


class Solution:
    def maxPoints(self, points):
        if len(points) < 3:
            return len(points)

        count = {}
        for point in points:
            point = tuple(point)
            count[point] = count.get(point, 0) + 1

        length = len(points)
        print("the length is: ", length)
        max_point_list = []
        for i in range(length):
            diff = {}
            for j in range(i+1, length):
                if points[i] == points[j]:
                    continue
                else:
                    dy = points[i][0] - points[j][0]
                    dx = points[i][1] - points[j][1]
                    # 忽略了除数为0的情况
                    if dx == 0:
                        k = points[i][0]
                        b = None
                        print("the demo is zero")
                    else:
                        k = dy / dx
                        b = points[i][1] - k * points[i][0]

                    diff[(k, b)] = diff.get((k, b), count[tuple(points[i])]) + 1

            print("diff: ", diff)
            # 忽略了列表为None的情况，为空时表明与当前数字一致
            if list(diff.values()):
                max_point = max(list(diff.values()))
                max_point_list.append(max_point)
            else:
                max_point_list.append(count[tuple(points[i])])

        return max(max_point_list)


# class Solution:
#     def maxPoints(self, points) -> int:
#         k_b = {}
#         repeated = {}
#         points = [tuple(point) for point in points]
#         # 统计每个point的个数
#         for point in points:
#             if point in repeated:
#                 repeated[point] += 1
#             else:
#                 repeated[point] = 1
#         # 去重
#         points = list(set(points))
#
#         # 特殊情况
#         if len(points) < 3:
#             total = 0
#             for key in repeated.keys():
#                 total += repeated[key]
#             return total
#
#         # 正常情况
#         max_nums = 2
#         for i in range(len(points)):
#             for j in range(i + 1, len(points)):
#                 x1, y1 = points[i]
#                 x2, y2 = points[j]
#
#                 if x1 == x2:
#                     k = x1
#                     b = math.inf
#                 else:
#                     k = (y1 - y2) / (x1 - x2)
#                     b = y1 - x1 * k
#
#                 if (k, b) not in k_b:
#                     k_b[(k, b)] = [points[i], repeated[points[i]] + repeated[points[j]]]
#                 else:
#                     if points[i] == k_b[(k, b)][0]:
#                         k_b[(k, b)][1] += repeated[points[j]]
#                         max_nums = max(k_b[(k, b)][1], max_nums)
#         return max_nums


if __name__ == "__main__":
    s = Solution()
    points = [[-435, -347], [-435, -347], [609, 613], [-348,-267],
              [-174,-107],[87,133],[-87,-27],[-609,-507],[435,453],
              [-870,-747],[-783,-667],[0,53],[-174,-107],[783,773],
              [-261,-187],[-609,-507],[-261,-187],[-87,-27],[87,133],
              [783,773],[-783,-667],[-609,-507],[-435,-347],[783,773],[-870,-747],
              [87,133],[87,133],[870,853],[696,693],[0,53],[174,213],[-783,-667],
              [-609,-507],[261,293],[435,453],[261,293],[435,453]]
    result = s.maxPoints(points)
    print(result)
